package com.nl.search;

public class RotateArrayMin {

	
	/**
	 * 旋转数组最小值<br>
	 * 1.left一直指向最左侧的递增数组，right一直指向右侧递增数组
	 *2.中间值位于数组左侧，左侧指针赋值为中间值位置 
	 * @param rotateArr
	 * @return
	 */
	public static int rotateMin(final int[]rotateArr){
		int left=0,right=rotateArr.length-1;
		//递增数组最小值就是left
		int mid=left;
		while(rotateArr[left]>=rotateArr[right]){
			if(left+1==right){
				mid=right;
				break;
			}
			mid=(left+right)/2;
			//中间值和左右值相同的时候，无法确定是中间值在哪个序列，顺序查找
			if(rotateArr[left] == rotateArr[right] && rotateArr[mid]==rotateArr[left]){
				int min=rotateArr[left];
				for(int i=1+left;i<=right;i++){
					if(min>rotateArr[i]){
						min = rotateArr[i];
					}
				}
				return min;
			}
			//在左侧升序序列中
			if(rotateArr[mid]>=rotateArr[left]){
				left=mid;
			}else{
				//在右侧升序序列中
				right=mid;
			}
		}

		return rotateArr[mid];
	}
	
	public static void main(String[] args) {
		System.out.println(rotateMin(new int[]{3,4,5,8,1,2}));
		System.out.println(rotateMin(new int[]{1,1,1,1,0,1,1,1}));
	}

}
